
// 题目：https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=23289&ru=%2Fpractice%2F57aa0bab91884a10b5136ca2c087f8ff&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
// 思路1：1.根据根节点，找到左右子序列；判断右序列的所有值，是不是否和均大于的根节点值；
// 思路2：1.参考实现2，对边界的处理更简单些；2.递归的时候不用再生成额外的局部变量vec；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


#include <algorithm>
#include <cstddef>
#include <vector>

class Solution {
  public:
    bool isPostTree(vector<int> sequence) {
        if (sequence.size() == 1 || sequence.size() == 0) return true;
        int root_val = sequence.back();
        auto left_arr_end_iter = sequence.begin();

        for (auto iter = sequence.begin(); iter != sequence.end()-1; ) {
            if (*iter > root_val) {
                break;
            }
            left_arr_end_iter = ++iter;
        }
        for (auto iter = left_arr_end_iter; iter != sequence.end()-1; ++iter) {
           if (*iter < root_val) { 
                return false;
            }
        }

        auto left_arr = std::vector<int> (sequence.begin(), left_arr_end_iter);
        auto right_arr = std::vector<int> (left_arr_end_iter, sequence.end() - 1);

        return isPostTree(left_arr) && isPostTree(right_arr);

    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return false;
        return isPostTree(sequence);
    }
};

// 升级版本
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if(n == 0) return false;    // 注意审题, 约定空树不是二叉搜索树
        return check(sequence, 0, n - 1);
    }
 
    bool check(vector<int>& sequence, int l, int r){
        if(l >= r) return true;    // 若当前子树只有一个节点
 
        int root = sequence[r];    // 当前子树的根节点
 
        // 划分出右子树
        int j = r - 1;
        while(j >= l && sequence[j] > root) j--;
 
        // 检查左子树是不是存在大于根节点的数
        for(int i = l; i <= j; i++){
            if(sequence[i] > root) return false;
        }
 
        // 分治法检查左子树和右子树
        return check(sequence, l, j) && check(sequence, j + 1, r - 1);
    }
};